Decision Tree

Author : Benjamin142857

决策树（Decision Tree）：一种统计学上分析数据的方法，目的在于了解两个或多个变数间是否相关、相关方向与强度，并建立数学模型以便观察特定变数来预测研究者感兴趣的变数。

难度评估：⭐️⭐️:star:

决策树主要算法：

1. 迭代二叉树 - 3代 (ID3)
2. C4.5 和 C5.0
3. 分类与回归树 (CART)
4. 卡方自动交互检测 (CHAID)
5. 快速无偏有效统计树 (QUEST)

常用于：分类

阅读前建议先看：Information Theory NoteInformation Theory .md)

ID3 (Iterative Dichotomiser 3) - 迭代二叉树三代

ID3：ID3算法是决策树的一种，它是基于奥卡姆剃刀原理的，即用尽量用较少的东西做更多的事。ID3算法,即Iterative Dichotomiser3，迭代二叉树三代，是Ross Quinlan发明的一种决策树算法，这个算法的基础就是上面提到的奥卡姆剃刀原理，越是小型的决策树越优于大的决策树，尽管如此，也不总是生成最小的树型结构，而是一个启发式算法。

核心思想：以信息增益来度量属性的选择，选择分裂后信息增益最大的属性进行分裂。

目录：

1. 奥卡姆剃刀
2. 信息增益
3. 算法过程

• Occam’s razor - 奥卡姆剃刀

奥卡姆剃刀是机器学习里的一个重要哲学，核心思想就是 “化繁为简” ，对在模型学习时遇到的under-fitting与overfitting现象有重要意义。在决策树ID3算法中，基础就是上面提到的奥卡姆剃刀原理，因为决策树很容易过拟合，所以往往越是小型的树，就越优于大型的树，就有了ID3中的 “D” - Dichotomiser(叉状二分法)的概念，就是每个结点尽可能的取两个分支。

Occam’s Razor 的更详细内容请看”Machine Learing 番外篇 (一) - 机器学习的哲学 - 机器学习的哲学.md)”

• Information Gain - 信息增益

$IG$ 计算公式：$IG_{特征} = Entropy_{总} - Entropy_{特征}$

​ $= -\sum_{k=1}^n\sum_{q=1}^{y_{typenum}}[P_k(x_q)·log_2P_k(x_q)] -\sum_{i=1}^{x_{typenum}}\sum_{j=1}^{y_{typenum}}[P_i(x_j)·log_2P_i(x_j)]$

公式说明：

1. $n$ : 所有样本的总类数

2. $ x_{typenum}$ : 此特征的（分箱/区域）数

3. $y_{typenum}$: 对应所属区域的标签类数

计算信息增益的作用：为了确定哪个特征作为相应节点，计算其信息增益可以知道该特征的重要程度（该特征单独作用对分类的影响大小），信息增益越大的特征，越重要，所以选最大的作为节点。

信息增益在DT的更详细内容请看 “Decision Tree 番外篇（一）- Entropy 与 IG 在DT中的意义 - Entropy&GI在DT中的意义.md)”

• ID3算法过程

如果了解了信息增益的计算，那么ID3的算法过程就很简单。

我们的第一个根节点就是选所有特征中的 $IG_{max}$ 特征。然后延这个根节点分出2~3个支（根据奥卡姆剃刀，这里的根不要太支，就是在计算特征间IG之前，要对特征内区域的划分（即连续数值型特征的分箱，多离散型数值特征的剪枝）选出最优划分法，剪枝更详细

C4.5 和C5.0 （Classification 4.5&5.0）

待补

CART (Classification & Regression Tree) - 分类与回归树

待补

CHAID (CHi-squared Automatic Interaction Detector) - 卡方自动检验

待补

QUEST (Quick Unbiased Efficient Statistical Tree ) - 快速无偏有效统计树

待补

• Entrory
• ID3
• IG
• set DT
• Discretization
  1. Multi-way split
  2. Binary split
• Gini Index
  1. CART
  2. Gini split
• Misclassification Error

附录：

Decision Tree 番外篇（一）- Entropy 与 IG 在DT中的意义 - Entropy&GI在DT中的意义.md)

(-)Decision Tree番外篇（二）- 连续数值的分箱 与 剪枝

Machine Learing 番外篇 (一) - 机器学习的哲学 - 机器学习的哲学.md)

(-)Python代码实现决策树

(-)Matplotlib画树图

赏

thanks~~~ (⊙v⊙)

支付宝

微信